package merge_sort;

public class reversePairs {
    int[] tem;
    int ret;

    public int reversePairs(int[] nums) {
        int n = nums.length;
        ret = 0;
        tem = new int[n];
        mergeSort(nums, 0, n - 1);
        return ret;
    }

    void mergeSort(int[] nums, int left, int right) {
        if (left >= right)
            return;
        // 找中间值,划分[left,mid][mid+1,right]两个区间
        int mid = (right + left) / 2;
        // 先对两个区间排序
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);

        // 处理⼀左⼀右 - 先计算翻转对,记录ret
        int cur1 = left, cur2 = mid + 1, i = left;
        // 升序版本
        while (cur2 <= right) {
            while (cur1 <= mid && nums[cur2] >= nums[cur1] / 2.0)
                cur1++;
            if (cur1 > mid)
                break;
            ret += mid - cur1 + 1;
            cur2++;
        }

        // 然后对两个数组升序排序
        cur1 = left;
        cur2 = mid + 1;
        i=0;
        while (cur1 <= mid && cur2 <= right) {
            if (nums[cur1] <= nums[cur2]) {
                tem[i++] = nums[cur1++];
            } else {

                tem[i++] = nums[cur2++];
            }
        }
        // 处理余下数组
        while (cur1 <= mid)
            tem[i++] = nums[cur1++];
        while (cur2 <= right)
            tem[i++] = nums[cur2++];

        // 更新原数组
        for (i = left; i <= right; i++) {
            nums[i] = tem[i - left];
        }
    }
}
